/*  Copyright 2010 Daniel Brasil Magnani
 *  Created on: Dec 20, 2010
 *      Author: daniel
 */

#include "solutionDS.h"

using std::vector;
using std::swap;
using std::sort;

bool Compare(const int *a, const int *b) {
  return (a[1] < b[1]);
}

void Solution::UpdateStructures() {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int counter;
  for (int i = 0; i < constraint_size_; i++) {

    max_profit_[i][1] = 0;
    for (int j = 0; j < solution_size_+yesterday_size_; j++) {
      M1_[i][j] = 0;
      M2_[i][j] = 0;
      M3_[i][j] = 0;
      M4_[i][j] = 0;
      M5_[i][j] = 0;
      M6_[i][j] = 0;
      M7_[i][j] = 0;
      counter = 0;
      for (int l = 0; l < constraint_list[i].p; l++) {
        if ( j < solution_size_ )
          M1_[i][j] += solution_[j+l].constraints[i];
        if ( j >= yesterday_size_ )
          counter += solution_[j-l].constraints[i];
      }
      if ( counter > constraint_list[i].n )
        max_profit_[i][1] += counter - constraint_list[i].n;
      if ( M1_[i][j] > constraint_list[i].n ) {
        if ( j > 0 ) {

          M2_[i][j] = M2_[i][j-1]+1;
          M3_[i][j] = M3_[i][j-1]+1;
        } else {
          M2_[i][j] = 1;
          M3_[i][j] = 1;
        }
      } else if ( M1_[i][j] == constraint_list[i].n ) {
        if ( j > 0 ) {
          M2_[i][j] = M2_[i][j-1];
          M3_[i][j] = M3_[i][j-1]+1;
        } else {
          M2_[i][j] = 0;
          M3_[i][j] = 1;
        }
      } else {
        if ( j > 0 ) {
          M2_[i][j] = M2_[i][j-1];
          M3_[i][j] = M3_[i][j-1];
        } else {
          M2_[i][j] = 0;
          M3_[i][j] = 0;
        }
      }
    }
  }
  sort(max_profit_.begin(), max_profit_.end(), Compare);
}

int Solution::SwapVariation(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation = 0;

  if ( i-constraint_list[k].p > 0 )
    variation += M3_[k][i] - M3_[k][i-constraint_list[k].p];
  else
    variation += M3_[k][i];

  if ( j-constraint_list[k].p > 0 )
    variation -= M2_[k][j] - M2_[k][j-constraint_list[k].p];
  else
    variation -= M2_[k][j];

  return variation;
}

int Solution::SwapCost(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation;
  variation = 0;
  if ( solution_[i].constraints[k] != solution_[j].constraints[k] ) {
    if ( solution_[i].constraints[k] < solution_[j].constraints[k] ) {
      variation = SwapVariation(i, j, k);
    } else {
      variation = SwapVariation(j, i, k);
    }
  }
  return variation;
}

void Solution::Swap(int i, int j) {
  swap(solution_[i], solution_[j]);
}

int Solution::RemoveCost(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation = 0;

  if ( M1_[k][i] > constraint_list[k].n )
    variation -= M1_[k][i] - constraint_list[k].n;

  int has_constraint = solution_[i].constraints[k];
  if ( has_constraint == 1 )
    variation -= M6_[k][i-1] - M6_[k][i-constraint_list[k].p];
  else
    variation += M5_[k][i-1] - M5_[k][i-constraint_list[k].p];

  return variation;
}

int Solution::InsertCost(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation = 0;

  variation = M1_[k][j] - solution_[j+constraint_list[k].p-1].constraints[k] +
               solution_[i].constraints[k] - constraint_list[k].n;
  if ( variation < 0 )
    variation = 0;

  int has_constraint = solution_[i].constraints[k];
  if ( has_constraint == 1 )
    variation -= M7_[k][i-1] - M7_[k][i-constraint_list[k].p];
  else
    variation += M4_[k][i-1] - M4_[k][i-constraint_list[k].p];

  return variation;
}

int Solution::InsertionCost(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation = 0;
  variation += InsertCost(i, j, k);
  variation += RemoveCost(i, j, k);

  return variation;
}

void Solution::Insertion(int i, int j) {
  Car temp_car;
  vector<Car>::iterator it;
  temp_car = solution_[i];
  it =  solution_.begin();
  advance(it,i);
  solution_.erase(it);

  it = solution_.begin();
  if ( i < j )
    advance(it,j-1);
  else
    advance(it,j);
  solution_.insert(it, temp_car);
}

int Solution::ReflectionCost(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation = 0;
  int counter1, counter2;
  if ( i > j )
    swap(i, j);

  counter1 = M1_[k][i-constraint_list[k].p+1] + solution_[i].constraints[k] +
             solution_[j].constraints[k];
  counter2 = M1_[k][j] + solution_[i].constraints[k] -
             solution_[j].constraints[k];
  if ( M1_[k][i-constraint_list[k].p+1] > constraint_list[k].n ) {
    variation -= M1_[k][i-constraint_list[k].p+1] - constraint_list[k].n;
  }
  if ( counter1 > constraint_list[k].n ) {
    variation += counter1 - constraint_list[k].n;
  }
  if ( M1_[k][j] > constraint_list[k].n ) {
    variation -= M1_[k][j] - constraint_list[k].n;
  }
  if ( counter2 > constraint_list[k].n ) {
    variation += counter2 - constraint_list[k].n;
  }
  for (int l = 1;l < constraint_list[k].p-1;l++) {
//    printf("Min: %d Max: %d\n", i-constraint_list[k].p+l, j+constraint_list[k].p-l);
    counter1 = counter1 - solution_[i-constraint_list[k].p+l].constraints[k] +
               solution_[j-l].constraints[k];
    counter2 = counter2 - solution_[j+constraint_list[k].p-l].constraints[k] +
               solution_[i+l].constraints[k];
    if ( M1_[k][i-constraint_list[k].p+l+1] > constraint_list[k].n ) {
      variation -= M1_[k][i-constraint_list[k].p+l+1] - constraint_list[k].n;
    }
    if ( counter1 > constraint_list[k].n ) {
      variation += counter1 - constraint_list[k].n;
    }
    if ( M1_[k][j-l] > constraint_list[k].n ) {
      variation -= M1_[k][j-l] - constraint_list[k].n;
    }
    if ( counter2 > constraint_list[k].n ) {
      variation += counter2 - constraint_list[k].n;
    }
  }

  return variation;
}

void Solution::Reflection(int i, int j) {
  if ( i > j )
    swap(i, j);
  for (int l = 0; l <= (j-i)/2; l++) {
    swap(solution_[i+l], solution_[j-l]);
  }
}

int Solution::ShuffleCost(int i, int j, int k) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation = 0;
  int counter;
  if ( i > j )
    swap(i, j);

  counter = M1_[k][i-constraint_list[k].p+1] - solution_[i].constraints[k] +
            solution_[map_[i]].constraints[k];
  if ( M1_[k][i-constraint_list[k].p+1] > constraint_list[k].n ) {
    variation -= M1_[k][i-constraint_list[k].p+1] - constraint_list[k].n;
  }
  if ( counter > constraint_list[k].n ) {
    variation += counter - constraint_list[k].n;
  }
  for (int l = i-constraint_list[k].p+2;l <= j;l++) {
    counter = counter - solution_[map_[l-1]].constraints[k] +
               solution_[map_[l+constraint_list[k].p-1]].constraints[k];
    if ( M1_[k][l] > constraint_list[k].n ) {
      variation -= M1_[k][l] - constraint_list[k].n;
    }
    if ( counter > constraint_list[k].n ) {
      variation += counter - constraint_list[k].n;
    }
  }


  return variation;
}

void Solution::Shuffle(int i, int j) {
  if ( i > j )
    swap(i, j);

  vector<Car> temp_cars;
  vector<Car>::iterator it;
  temp_cars.reserve(j-i+1);
  it = solution_.begin();
  advance(it,i);
  copy(it, it+j-i+1, back_inserter(temp_cars));

  for (int l = i;l <= j;l++)
    solution_[l] = temp_cars[map_[l]-i];

}

std::vector<Car> Solution::get_solution() {
  return solution_;
}

Solution::Solution(const std::vector<Car> &solution) {
  vector<Constraint> constraint_list;
  vector<Car> yesterday_cars;
  vector<Car> today_cars;
  constraint_list = Instance::get_instance()->get_constraint_list();
  yesterday_cars = Instance::get_instance()->get_yesterday_cars();
  today_cars = Instance::get_instance()->get_today_cars();

  solution_.reserve(solution.size()+yesterday_cars.size());
  copy(solution.begin(), solution.end(), back_inserter(solution_));
  constraint_size_ = constraint_list.size();
  solution_size_ = solution_.size();
  yesterday_size_ = yesterday_cars.size();
  map_ = new int[solution_size_+yesterday_size_];
  max_profit_.resize(constraint_size_);

  M1_.resize(constraint_size_);
  M2_.resize(constraint_size_);
  M3_.resize(constraint_size_);
  M4_.resize(constraint_size_);
  M5_.resize(constraint_size_);
  M6_.resize(constraint_size_);
  M7_.resize(constraint_size_);
  // Dummya cars
  Car temp_car;
  temp_car.identifier = 0;
  temp_car.constraints = new int[constraint_size_];
  for (int i = 0; i < constraint_size_; i++) {
    temp_car.constraints[i] = 0;
    M1_[i].resize(solution_size_+yesterday_size_);
    M2_[i].resize(solution_size_+yesterday_size_);
    M3_[i].resize(solution_size_+yesterday_size_);
    M4_[i].resize(solution_size_+yesterday_size_);
    M5_[i].resize(solution_size_+yesterday_size_);
    M6_[i].resize(solution_size_+yesterday_size_);
    M7_[i].resize(solution_size_+yesterday_size_);
    max_profit_[i] = new int[2];
    max_profit_[i][0] = i;
    max_profit_[i][1] = 0;
  }
  for (int i = 0; i < yesterday_cars.size() ; i++) {
    solution_.push_back(temp_car);
  }



}

int Solution::ChooseTransformation(int random) {
  if ( random < 72 )
    return 1;
  if ( random < 88 )
    return 2;
  if ( random < 99 )
    return 3;
  else
    return 4;
}

int Solution::ChooseVariant(int random) {
  if ( random < 66 )
    return 1;
  if ( random < 68 )
    return 2;
  if ( random < 70 )
    return 3;
  if ( random < 72 )
    return 4;
  if ( random < 80 )
    return 1;
  if ( random < 88 )
    return 5;
  if ( random < 95 )
    return 1;
  if ( random < 99 )
    return 5;
  else
    return 1;
}

void Solution::GetCars(int *cars, int variant) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int i,j;
  switch (variant) {
    case 1: { //Generic
      i = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
      j = i;
      while ( j == i )
        j = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
      break;
    }
    case 2: { //Similar
      i = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
      int similarity = 0;
      j = i;
      while ( j == i || similarity == 0 ) {
        similarity = 0;
        j = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
        for ( int k = 0; k < constraint_size_; k++ ) {
          if ( solution_[i].constraints[k] == solution_[j].constraints[k] )
            similarity++;
        }
      }
      break;
    }
    case 3: { //Consecutive
      i = rand()%(solution_size_ - yesterday_size_ -1) + yesterday_size_;
      j = i+1;
      break;
    }
    case 4: { //Violation
      i = yesterday_size_;
      for ( int k = 0; k < constraint_size_; k++ ) {
        for ( int l = yesterday_size_; l < solution_size_; l++ ) {
          if ( M1_[k][l] > constraint_list[k].n ) {
            i = l;
            break;
          }
        }
      }
      j = i;
      while ( j == i )
        j = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
      break;
    }
    case 5: { //Denominator
      int k = rand()%constraint_size_;
      i = rand()%(solution_size_ - yesterday_size_ -
         constraint_list[k].p) + yesterday_size_;
      j = i+constraint_list[k].p;
      break;
    }
  }
  cars[0] = i;
  cars[1] = j;
}

void Solution::CreateMap(int i, int j) {

  int random;
  if ( i > j )
    swap(i, j);

  int max = j;
  for (int l = 0;l < solution_size_+yesterday_size_;l++)
    map_[l] = l;
  for (;max > i;max--) {
    random = i+rand()%(max-i);
    swap(map_[max], map_[random]);
  }
//  for (int l = 0;l < solution_size_+yesterday_size_;l++)
//    printf("%d ", map_[l]);
//  printf("\n");
}

int Solution::TransformationCost(int transformation, int i, int j, int k) {
  int variation = 0;
  switch (transformation) {
    case 1:
      variation = SwapCost(i, j, k);
      break;
    case 2:
      variation = InsertionCost(i, j, k);
      break;
    case 3:
      variation = ReflectionCost(i, j, k);
      break;
    case 4: {
      if ( k == max_profit_[0][0] )
        CreateMap(i, j);
      variation = ShuffleCost(i, j, k);
      break;
    }
    default:
      variation = SwapCost(i, j, k);
      break;
  }
  return variation;
}

void Solution::Transformation(int transformation, int i, int j) {
  switch (transformation) {
    case 1:
      Swap(i, j);
      break;
    case 2:
      Insertion(i,j);
      break;
    case 3:
      Reflection(i, j);
      break;
    case 4:
      Shuffle(i, j);
      break;
    default:
      Swap(i, j);
      break;
  }
}

int Solution::LocalSearch(float time_limit) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance()->get_constraint_list();

  int variation;
  int total_variation;
  int transformation;
  int variant;
  int* cars = new int[2];
  int remaining_profit;
  int visits = 0;
  int changes = 0;

  UpdateStructures();

  Chronometer chronometer;
  chronometer.Time();
  while ( chronometer.Value() < time_limit ) {
    int random = rand()%100;
    variant = ChooseVariant(random);
    transformation = ChooseTransformation(random);
    //Force variant to be generic
    GetCars(cars, 1);
    int i = cars[0];
    int j = cars[1];

    total_variation = 0;
    remaining_profit = 0;
    for ( int k = 0; k < constraint_size_; k++ ) {
      remaining_profit += max_profit_[k][1];
    }
    if ( remaining_profit == 0 ) {
      printf("0 %lf\n", chronometer.dValue());
      return true;
    }
    for ( int k = 0; k < constraint_size_; k++ ) {
      total_variation += TransformationCost(transformation, i, j, max_profit_[k][0]);
      remaining_profit -= max_profit_[k][1];
      if ( total_variation > remaining_profit )
        break;
    }

    if ( total_variation <= 0 ) {
//      printf("Mudou: %d e %d. Trans: %d\n", i, j, transformation);
      Transformation(transformation, i, j);
      UpdateStructures();
//      PrintCars();
      changes++;
    }
    visits++;
  }
  remaining_profit = 0;
  for ( int k = 0; k < constraint_size_; k++ ) {
    remaining_profit += max_profit_[k][1];
  }
  printf("%d %lf\n", remaining_profit, time_limit);
  return true;
}
